BZOJ 4071 巴邻旁之桥

Description

一条东西走向的穆西河将巴邻旁市一分为二,分割成了区域 A 和区域 B。
每一块区域沿着河岸都建了恰好 1000000001 栋的建筑,每条岸边的建筑都从 0 编号到 1000000000。相邻的每对建筑相隔 1 个单位距离,河的宽度也是 1 个单位长度。区域 A 中的 i 号建筑物恰好与区域 B 中的 i 号建筑物隔河相对。
城市中有 N 个居民。第 i 个居民的房子在区域 Pi 的 Si 号建筑上,同时他的办公室坐落在 Qi 区域的 Ti 号建筑上。一个居民的房子和办公室可能分布在河的两岸,这样他就必须要搭乘船只才能从家中去往办公室,这种情况让很多人都觉得不方便。为了使居民们可以开车去工作,政府决定建造不超过 K 座横跨河流的大桥。
由于技术上的原因,每一座桥必须刚好连接河的两岸,桥梁必须严格垂直于河流,并且桥与桥之间不能相交。当政府建造最多 K 座桥之后,设 Di 表示第 i 个居民此时开车从家里到办公室的最短距离。请帮助政府建造桥梁,使得 D1+D2+⋯+DN 最小。

Input

输入的第一行包含两个正整数 K 和 N,分别表示桥的上限数量和居民的数量。
接下来 N 行,每一行包含四个参数:Pi,Si,Qi 和 Ti,表示第 i 个居民的房子在区域 Pi 的 Si 号建筑上,且他的办公室位于 Qi 区域的 Ti 号建筑上。

Output

输出仅为一行,包含一个整数,表示 D1+D2+⋯+DN 的最小值。

Sample Input

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

Sample Output

24

Hint

子任务
所有数据都保证:Pi 和 Qi 为字符 “A” 和 “B” 中的一个, 0≤Si,Ti≤1000000000,同一栋建筑内可能有超过 1 间房子或办公室(或二者的组合,即房子或办公室的数量同时大于等于 1)。
子任务 1 (8 分)
K=1
1≤N≤1000
子任务 2 (14 分)
K=1
1≤N≤100000
子任务 3 (9 分)
K=2
1≤N≤100
子任务 4 (32 分)
K=2
1≤N≤1000
子任务 5 (37 分)
K=2
1≤N≤100000

Solution

首先距离变成所有异侧点到桥的距离和
K=1,初中数学题,取个中位数就行
K=2,发现一对点选择走哪座桥只很据中点判,枚举重点两边做K=1的情况就可以了
(线段树+不离散化常数有点大)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>

#define maxn 100000+5
#define maxm 200000+5
#define maxt 6000000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct segment{
int l,r,mid;
}seg[maxn];

struct segtree{
int s[2];
int num;ll sum;
}tr[maxt];

ll ans,res;
int disc[maxm];
int root[2],size;
int n,m,k,upper=1000000000;

bool comp(segment a,segment b)
{

return a.mid<b.mid;
}

void update(int x)
{

int l=tr[x].s[0],r=tr[x].s[1];
tr[x].sum=tr[l].sum+tr[r].sum;
tr[x].num=tr[l].num+tr[r].num;
}

void insert(int &x,int l,int r,int p,int w)
{

if( p<l || r<p ) return ;
if( x==0 ) x=++size;
if( l==r ){
tr[x].sum+=l*w,tr[x].num+=w;
return ;
}
insert(tr[x].s[0],l,(l+r)/2,p,w);
insert(tr[x].s[1],(l+r)/2+1,r,p,w);
update(x);
}

ll query(int x,int l,int r,int p)
{

if( tr[x].num<=p ) return tr[x].sum;
if( l==r ) return (ll)l*p;
int ls=tr[tr[x].s[0]].num;
if( p<=ls ) return query(tr[x].s[0],l,(l+r)/2,p);
return tr[tr[x].s[0]].sum+query(tr[x].s[1],(l+r)/2+1,r,p-ls);
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("4071.in","r",stdin);
freopen("4071.out","w",stdout);
#endif
scanf("%d%d",&k,&n);
for(int i=1;i<=n;i++){
char a[5],b[5];
m++;
scanf("%s%d%s%d\n",a,&seg[m].l,b,&seg[m].r);
if( seg[m].l>seg[m].r ) swap(seg[m].l,seg[m].r);
if( a[0]==b[0] ){
res+=seg[m].r-seg[m].l,m--;
continue;
}
seg[m].mid=seg[m].l+seg[m].r;
}
if( k==1 ){
for(int i=1;i<=m;i++)
disc[2*i-1]=seg[i].l,disc[2*i]=seg[i].r;
sort(disc+1,disc+2*m+1);
ll cur=disc[m];
for(int i=1;i<=2*m;i++) ans+=abs(cur-disc[i]);
}
else{
sort(seg+1,seg+m+1,comp);
for(int i=1;i<=m;i++)
insert(root[1],0,upper,seg[i].l,1),insert(root[1],0,upper,seg[i].r,1);
if( m!=0 ) ans=LLONG_MAX;
for(int i=1;i<=m;i++){
insert(root[0],0,upper,seg[i].l,1);
insert(root[0],0,upper,seg[i].r,1);
insert(root[1],0,upper,seg[i].l,-1);
insert(root[1],0,upper,seg[i].r,-1);
ll cur=tr[root[0]].sum-2*query(root[0],0,upper,i)+tr[root[1]].sum-2*query(root[1],0,upper,m-i);
ans=min(ans,cur);
}
}
printf("%lld",ans+res+m);
return 0;
}